Compressive sensing (CS) is a recently developed technique. Considering the fact that a large part of natural and artificial signals have the sparse or near sparse property, the compressive sensing technique can find applications in many different areas like compressive imaging, compressive sampling, signal processing, data stream computing, and combinatorial group testing, etc. The basic idea of compressive sensing is that a sparse signal x (a signal is referred to as sparse if it contains much more zero elements than non-zero elements) with length-N can be accurately recovered from a linear measurement y=Ax of length-M, wherein A is the M×N measurement matrix, M<<N.
The reconstruction can be performed through minimizing ∥x∥0 that explains the measurement vector. As this minimization problem is NP hard, sub-optimal algorithms have been investigated. Major classes of computationally feasible sparse signal recovery algorithms include convex relaxation, which approximates the l0 minimization problem by an lp minimization problem with p often chosen as 1 and solves this problem using convex optimization; matching pursuit, which iteratively refines a sparse solution by successively identifying one or more components that yield the greatest quality improvement; and Bayesian framework, which assumes a priori distribution that favors sparsity for the signal vector, and uses a maximum a posteriori estimator to incorporate the observation. Despite their relatively good performance in practice, they are most suitable for signals with continuous values. For sparse signals with digital values, e.g., when dealing with monochrome images, these algorithms are less sufficient as they cannot exploit the digital nature of the source, which, if utilized properly, can greatly enhance the recovery accuracy.
Therefore, there is a need of a new compressive sensing technique that can fully exploit the digital nature of signals.
In addition, in almost all applications, it is preferred that the measurement matrix A is sparse, i.e., it contains much more zero entries than non-zero entries in each column. The advantages of sparse measurement matrices include low computational complexity in both encoding and decoding, easy incremental updates to signals, and low storage requirement, etc. Much research has been devoted to CS with sparse measurement matrices, but most of them fail to achieve the linear decoding complexity and performance bound at the same time. Typical examples of existing algorithms include matching pursuit and convex optimization. The matching pursuit type of algorithms can asymptotically achieve the lower bound of the sketch length with a linear recovery complexity. However, numerical results have shown that the empirical sketch lengths needed in this type of algorithms are always much higher than the asymptotic bound. The convex optimization type of algorithms, on the other hand, can achieve the lower bound of the sketch length both asymptotically and empirically, which indicates an advantage in terms of measurement number in practices. For example, with the number of non-zero elements K=50 and signal length N=20000, it was shown that matching pursuit needs about 2000 measurements while convex optimization needs only about 450 measurements. One major disadvantage of the convex optimization type of algorithms is their higher recovery complexity, which grows in a polynomial order with the signal length N as O(N3).
Therefore, there is a need of a new compressive sensing technique that can achieve the linear decoding complexity and lower bound of sketch length empirically at the same time, with sparse measurement matrices.